package violentRecursion;
/**
 * @className: LeetCode_221
 * @Description: 最大正方形
 * @author: kunkun
 * @date: 2025/7/10 17:31
 */
public class LeetCode_221 {

    public int maximalSquare(char[][] matrix) {
        int[][] dp = new int[matrix.length][matrix[0].length];
        int res = 0;
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = (matrix[i][0]=='1')?1:0;
            res=Math.max(res,dp[i][0]);
        }
        for (int j = 0; j < dp[0].length; j++) {
            dp[0][j] = (matrix[0][j]=='1')?1:0;
            res=Math.max(res,dp[0][j]);
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                if (matrix[i][j]=='0'){
                    dp[i][j]=0;
                }else {
                    dp[i][j]=findMin(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1;
                }
                res=Math.max(res,dp[i][j]);
            }
        }
        return res*res;


    }

    public int findMin(int a,int b,int c){
        return Math.min(a,Math.min(b,c));
    }
}

